class Solution {
	int* a;
public:
	int numWays(int n) {
		 a = new int[n+1];
		for (int i = 0; i < n+1; i++)
		{
			a[i] = -1;
		}
		return fi(n);
	}
	int fi(int n)
	{
		if (n <= 1)
			return n;
		if (a[n]!=-1)
			return a[n];
		else
		{
			int sum = (fi(n - 1) + fi(n - 2)) % 1000000007;
			a[n] = sum;
			return sum;
		}
	}

};